1665B - Array Cloning Technique - CodeForces Solution


constructive algorithms sortings

Please click on ads to support us..

Python Code:

for _ in range(int(input())):
    n=int(input())
    l=list(map(int,input().split()))
    d={}
    maxi=-10000
    for i in l:
        if i in d:
            d[i]+=1
            maxi=max(maxi,d[i])
        else:
            d[i]=1
            maxi=max(maxi,d[i])
    if(maxi==n):
        print(0)
    else:
        cnt=1
        while(maxi<=n):
            if(maxi+maxi>=n):
                cnt+=(n-maxi)
                break
            cnt+=maxi
            maxi*=2
            cnt+=1
        print(cnt)

C++ Code:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long int t;
    cin >> t;
    while (t--)
    {
        long long int n;
        cin >> n;
        vector<long long int> v(n);
        map<long long int, long long int> m;
        for (long long int i = 0; i < n; i++)
        {
            cin >> v[i];
            m[v[i]]++;
        }
        long long int val;
        long long int maximum = INT_MIN;
        for (auto it : m)
        {
            if (it.second >= maximum)
            {
                val=it.first;
                maximum = it.second;
            }
        }
        long long int count = 0;
        while (1)
        {
            if(m[val] == n)
            {
                break;
            }
            count++;
            long long int k = n - m[val];
            long long int l = m[val];
            if (k >= l)
            {
                m[val]+=l;
                k=k-l;
                count+=l;
            }
            else{
                m[val]+=k;
                count+=k;
                break;
                k=0;
            }
        }
        cout << count << endl;
    }
    return 0;
}


Comments

Submit
0 Comments
More Questions

1625C - Road Optimization
1715D - 2+ doors
267A - Subtractions
1582A - Luntik and Concerts
560A - Currency System in Geraldion
946A - Partition
1068B - LCM
1692E - Binary Deque
679A - Bear and Prime 100
488A - Giga Tower
14A - Letter
1150A - Stock Arbitraging
1552A - Subsequence Permutation
1131F - Asya And Kittens
1475F - Unusual Matrix
133B - Unary
1547A - Shortest Path with Obstacle
624A - Save Luke
1238A - Prime Subtraction
1107C - Brutality
1391B - Fix You
988B - Substrings Sort
312A - Whose sentence is it
513A - Game
1711E - XOR Triangle
688A - Opponents
20C - Dijkstra
1627D - Not Adding
893B - Beautiful Divisors
864B - Polycarp and Letters